package review.Day_0406;

import java.util.Stack;

/**
 * @author zxc
 * @date 2023/04/06 22:40
 **/
public class Solution03 {
    /**
     * 思路 ：
     * 1.若是某个对象的右侧队列中不存在比其高的元素，
     * ===>
     * 则该对象的可见元素数 == 在该元素的右侧队列中，以其右侧第一个元素为初始值，逐步递增的元素总数;
     * 2.若是某个对象的右侧队列中存在比其高的元素，
     * ===>
     * 则该对象的可见元素数 == 在该元素的右侧队列中，以其右侧第一个元素为初始值，逐步递增（小于当前对象值）的元素总数
     *                     + 右侧队列中，第一个大于等于该对象值的元素;
     * 3.逆序遍历 + 辅助栈（从栈底到栈顶-单调递减）
     * （1）选择逆序遍历heights数组中所有元素，以O(n)时间复杂度，获取到各个元素右侧队列中的所有递增元素;
     * （2）辅助栈，用来存储 当前元素右侧队列中的所有递增元素;
     *
     */
    public int[] canSeePersonsCount(int[] heights) {
        // 获取heights数组中的元素总数
        int len = heights.length;
        // 创建结果数组，用来存储每个对象在其右侧队列中所能够看到的对象数;
        int[] result = new int[len];
        // 辅助栈，存储当前遍历数组元素，右侧递增元素;
        Stack<Integer> stack = new Stack<>();
        // 逆序遍历heights数组中每个对象
        for(int i = len - 1; i >= 0 ; i--){
            // 辅助栈不为空 && 当前正在遍历的元素，还未遇到第一个比起高的元素;
            while(!stack.isEmpty() && heights[i] > stack.peek()){
                // 统计 比当前遍历元素矮的可见元素数;
                result[i]++;
                // 由于该元素的存在，所遍历到的栈中元素都比该元素矮，
                // ===》比之更靠前的元素是不能够看到的，所以将该元素从栈中删除;
                stack.pop();
            }
            // （1）若是栈不为空，说明该元素右侧存在比其高的元素，所以 可见元素总数 = 比其矮的可见元素数 + 第一个比起高的可见元素：
            // （2）若是栈为空的话，则说明该元素右侧不存在比其高的元素，所以 可见元素总数 = 比起矮的可见元素数;
            if(!stack.isEmpty()){
                result[i]++;
            }
            // 无论如何，当前遍历的元素是必然会被加入到辅助栈中的;
            // 辅助栈中，所存储的元素是，以该元素为初始值，后续所有递增元素;
            // ===》 即，该辅助栈是符合 从栈底到栈顶-单调递减（从栈顶到栈底-单调递增）的特性;
            stack.push(heights[i]);
        }
        return result;
    }
}
